package oj;

public class LC23 {
    public ListNode mergeKLists(ListNode[] lists) {
        return merge(lists,0,lists.length-1);
    }
    private ListNode merge(ListNode[] lists,int l,int r){
        if(l>r){
            return null;
        }
        if(l==r){
            return lists[l];
        }
        int mid=(l+r)>>1;
        return mergeTwoLists(merge(lists,l,mid),merge(lists,mid+1,r));
    }
    private ListNode mergeTwoLists(ListNode a,ListNode b){
        if(a==null) return b;
        if(b==null) return a;
        ListNode dummyHead=new ListNode(0);
        ListNode last=dummyHead;
        while(a!=null && b!=null){
            if(a.val<b.val){
                last.next=a;
                a=a.next;

            }else{
                last.next=b;
                b=b.next;
            }
            last=last.next;
        }
        last.next=(a!=null?a:b);
        return dummyHead.next;
    }
}
